The present invention relates to a line-figure processor, and more particularly to an apparatus which generates a dot pattern forming a line segment from the coordinates of the starting point and the terminating point of the line segment.
In conventional line-figure processors, a dot pattern for a line segment extending between a given starting point and a given terminating point is produced from the coordinates of these points by means of interpolation. A typical method of the interpolation is Bresenham's algorithm, a detail of which is disclosed in "Algorithm for Computer Control of a Digital Plotter" (Bresenham, J. E., IBM System Journal, vol. 4, No 1, pp. 25-30, (1965).
The flow chart of FIG. 5 illustrates an outline of Bresenham's algorithm for 0 to 45 degrees of an angle between a given line segment and X axis. Let the coordinates of the starting and terminating points are (X.sub.o, Y.sub.0) and (X.sub.a, Y.sub.b), respectively. At the beginning, the differences in X and Y coordinates between the starting point and the terminating point, namely, a=.vertline.X.sub.a -X.sub.0 .vertline. and b=.vertline.Y.sub.b -Y.sub.0 .vertline., are calculated to supply a and b thereof to the first discriminant e.sub.1 =2b-a. Then, setting the value of K equal to 1, the coordinates of the first interpolating point (X.sub.1, Y.sub.1) are calculated as indicated in the flow chart of FIG. 5. In this calculation, when e.sub.1 &gt;0, a step 51 is selected and when e.sub.1 &lt;0, a step 52 is selected. In case the step 51 is selected, the coordinates of the first interpolating point and the second discriminant to be used in the next calculation are EQU (X.sub.1, Y.sub.1)=(X.sub.0, Y.sub.0 +1) EQU e.sub.2 =e.sub.1 +2(b-a)=4b-3a
respectively, and in case the step 52 is selected, the corresponding values are EQU (X.sub.1, Y.sub.1)=(X.sub.0 +1, Y.sub.0) EQU e.sub.2 =e.sub.1 +2b=4b-a
respectively. The coordinates of successive interpolating points are calculated sequentially by repeating a similar calculation. In case the angle between the given line segment and X axis is out of 0 to 45 degree range, the generating of the dot pattern is essentially the same as aforementioned.
It can be pointed out as one of drawbacks of the conventional method described above that it inherently consumes rather a long processing time. However, the overall speed of line figure processing will be improved significantly if dot patterns for horizontal and vertical line segments, which appear very frequently in most practical cases, are generated more quickly.